#include "TreeBuilder.h"
#include "SharedFileName.h"
#include <string>
#include <iostream>
#include <unordered_set>
#include <fstream>
#include <sstream>
#include <time.h>
#include <map>
#include <set>
using namespace std;

TreeBuilder::TreeBuilder(int non_root_node_size, string in_dir, string out_dir){
	this->reduction_factor = non_root_node_size;

	ExtractGraphStruct(in_dir);

	tree_root = NULL;

	DecomposeGraph(this->graph_adj_list);
}

TreeBuilder::~TreeBuilder(){
	for(int i = 0; i < built_nodes.size(); i++) delete built_nodes[i];
	built_nodes.clear();
}

void TreeBuilder::ExtractGraphStruct(string in_dir){
	string adj_file(in_dir);
	adj_file.append(sample_adjlist_file);
	ifstream graphAdj(adj_file.c_str());
	cout << "adj_file : " << adj_file << endl;
	if(!graphAdj.is_open()){
		cout << "canont open graph adjlist" << endl;
		exit(1);
	}

	string line;
	getline(graphAdj,line); // skip the first line
	int number_nodes = atoi(line.c_str());
	graph_adj_list.resize(number_nodes);

	int node_idx = 0;
	while(getline(graphAdj,line)){
		stringstream ss(line);
		int num_neighbours;
		ss >> num_neighbours;
		for(int i = 0; i < num_neighbours; i++){
			int neighbour;
			if(!(ss >> neighbour)){
				cout << "adjcency list problem" << endl;
				exit(1);
			}
			graph_adj_list[node_idx].insert(neighbour);
		}
		node_idx++;
	}
	graphAdj.close();
	cout << "finish reading adj list" << endl;
}

// this struction only serves an helper for decompose graph
struct StackElem{
	int node;
	vector<int> neighbour;

	StackElem(int _node){this->node = _node;};
};

int get_tree_height(vector<TreeNode*>& built_nodes, int current_node_idx, int current_height){
	TreeNode* current_node = built_nodes[current_node_idx];
	if(current_node->children.empty()) return current_height;
	int max_height = current_height;
	for(int i = 0; i < current_node->children.size(); i++){
		int child_height = get_tree_height(built_nodes,current_node->children[i],current_height+1);
		if(max_height < child_height){
			max_height = child_height;
		}
	}
	return max_height;
}

void TreeBuilder::DecomposeGraph(vector<unordered_set<int> >& adj_list){
	stack<StackElem> clique_stack;
	int num_nodes = adj_list.size();

	// indicate whether the node is visited before

	map<int,set<int>> node_degree_map; // keep the degree - node relationship
	for(int i = 0; i < num_nodes; i++) 
		node_degree_map[adj_list[i].size()].insert(i);
	vector<map<int,set<int>>::iterator> node_iter_vec(num_nodes);

	// store the iterator information in the node_iter_vec
	for(auto it = node_degree_map.begin(); it != node_degree_map.end(); it++){
		for(auto sit = it->second.begin(); sit != it->second.end(); sit++){
			node_iter_vec[*sit] = it;
		}
	}
		

	int node_left = num_nodes;
	clock_t find_time = 0; // time for finding node to reduce
	clock_t build_time = 0; // time for building clique

	// reduction phase, reduce node with degree that less than reduction_factor
	for(int degree = 1; degree <= reduction_factor; degree++){
		while(true){
			clock_t start = clock();

			int node = -1;

			// get the first element
			if(node_degree_map.begin()->first <= degree){
				set<int>& node_container =  node_degree_map.begin()->second;
				if(node_container.empty()){
					node_degree_map.erase(node_degree_map.begin());
					continue;
				}
				set<int>::iterator node_iter = node_container.begin();
				node = *node_iter;
				node_container.erase(node_iter); // delete this element
			}else{
				break;
			}
			find_time += (clock() - start);

			start = clock();
			node_left--;
			StackElem new_elem(node);
			// get all the neighbours and push to stack
			for(auto it = adj_list[node].begin(); it != adj_list[node].end(); it++){
				new_elem.neighbour.push_back(*it);
			}
			clique_stack.push(new_elem);

			// early termination
			if(new_elem.neighbour.size() == node_left){
				node_left = 0;
				break;
			}

			// build the clique
			int num_neigbours = new_elem.neighbour.size();
			for(int i = 0; i < num_neigbours; i++){
				int node_x = new_elem.neighbour[i];
				for(int j = 0; j < num_neigbours; j++){
					if(i == j) continue;
					int node_y = new_elem.neighbour[j];
					adj_list[node_x].insert(node_y);
					adj_list[node_y].insert(node_x);
				}
			}

			// remove edge between the node and its neighbours
			for(int i = 0; i < num_neigbours; i++) adj_list[new_elem.neighbour[i]].erase(node);

			// update iterator
			for(int i = 0; i < num_neigbours; i++){
				int neighbour_idx = new_elem.neighbour[i];
				if(adj_list[neighbour_idx].size() == node_iter_vec[neighbour_idx]->first) continue;
				set<int>& node_container = node_iter_vec[neighbour_idx]->second; // get the set container for this node
				node_container.erase(node_container.find(neighbour_idx)); // delet the old iterator
				node_degree_map[adj_list[neighbour_idx].size()].insert(neighbour_idx);
				node_iter_vec[neighbour_idx] = node_degree_map.find(adj_list[neighbour_idx].size()); // update the new iterator
			}

			build_time += (clock() - start);
			if(node_left % 10000 == 0){
				cout << "find time: " << ((double)find_time)/ CLOCKS_PER_SEC << " secs" << endl;
				cout << "build time: " << ((double)build_time)/ CLOCKS_PER_SEC << " secs" << endl;
			}
		}
		cout << "finish reduction for degree: " << degree << " with number of nodes left: " << node_left << endl;
	}

	int num_tree_nodes = 0;

	// creating the root
	int neighbour_idx = 0;
	vector<int> node_tree_idx(num_nodes,-1);

	if(node_left != 0){
		tree_root = new TreeNode(num_tree_nodes);
		for(auto it = node_degree_map.begin(); it != node_degree_map.end(); it++){
			set<int>& node_container = it->second;
			for(auto sit = node_container.begin(); sit != node_container.end(); sit++){
				tree_root->graph_nodes[*sit] = neighbour_idx++;
				node_tree_idx[*sit] = num_tree_nodes;
			}
		}
		built_nodes.push_back(tree_root);
	}else{
		StackElem top_elem = clique_stack.top();
		// create new nodes
		tree_root = new TreeNode(num_tree_nodes);
		tree_root->graph_nodes[top_elem.node] = neighbour_idx++;
		for(int i = 0; i < top_elem.neighbour.size(); i++)
			tree_root->graph_nodes[top_elem.neighbour[i]] = neighbour_idx++;
		for(auto it = tree_root->graph_nodes.begin(); it != tree_root->graph_nodes.end(); it++)
			node_tree_idx[it->first] = num_tree_nodes;
		built_nodes.push_back(tree_root);
		clique_stack.pop();
	}

	cout << "root size: " << tree_root->graph_nodes.size() << endl;
	cout << "tree node number: " << clique_stack.size() + 1 << endl;

	while(!clique_stack.empty()){
		StackElem top_elem = clique_stack.top();
		num_tree_nodes++;
		
		neighbour_idx = 0;
		// create new nodes
		TreeNode* new_node = new TreeNode(num_tree_nodes);
		new_node->graph_nodes[top_elem.node] = neighbour_idx++;
		for(int i = 0; i < top_elem.neighbour.size(); i++)
			new_node->graph_nodes[top_elem.neighbour[i]] = neighbour_idx++;
		for(auto it = new_node->graph_nodes.begin(); it != new_node->graph_nodes.end(); it++){
			if(node_tree_idx[it->first] == -1){
				node_tree_idx[it->first] = num_tree_nodes;
			}
		}


		// looking for the parent
		int parent_idx = -1;
		for(int i = 0; i < top_elem.neighbour.size(); i++){
			if(node_tree_idx[top_elem.neighbour[i]] > parent_idx){
				parent_idx = node_tree_idx[top_elem.neighbour[i]];
			}
		}

		if(parent_idx == -1){
			cout << "something goes wrong in the tree construction process" << endl;
			exit(1);
		}


		new_node->parent.push_back(parent_idx);
		built_nodes[parent_idx]->children.push_back(num_tree_nodes);

		// finally update the built tree node
		built_nodes.push_back(new_node);

		// remove the element
		clique_stack.pop();

		if(num_tree_nodes % 10000 == 0) cout << "finished adding " << num_tree_nodes << " number of nodes" << endl;
	}

	cout << "number of tree nodes: " << num_tree_nodes << endl;
	int max_tree_node_size = 0;
	for(int i = 0; i < built_nodes.size(); i++){
		if(built_nodes[i]->graph_nodes.size() > max_tree_node_size){
			max_tree_node_size = built_nodes[i]->graph_nodes.size();
		}
	}
	cout << "max tree width: " << max_tree_node_size << endl;

	// measure the height 
	cout << "tree height is: " << get_tree_height(built_nodes,0,1);



	//// print result
	//for(int i = 0; i < built_nodes.size(); i++){
	//	// print the node
	//	cout << "node: " << built_nodes[i]->node_idx << " with graph nodes: ";
	//	for(auto it = built_nodes[i]->graph_nodes.begin(); it != built_nodes[i]->graph_nodes.end(); it++)
	//		cout << it->first << " ";
	//	cout << endl;

	//	// print the pareint
	//	cout << "parent: ";
	//	for(int j = 0; j < built_nodes[i]->parent.size(); j++)
	//		cout << built_nodes[i]->parent[j] << " ";
	//	cout << endl;

	//	// print the chilren
	//	cout << "children: ";
	//	for(int j = 0; j < built_nodes[i]->children.size(); j++)
	//		cout << built_nodes[i]->children[j] << " ";
	//	cout << endl;
	//}
	//getchar();
}

int main(int argc, char *argv[]){

	if(argc != 2){
		cout << "wrong arguments for " << argv[0] << endl;
		cout << "1. input directory" << endl;
		exit(1);
	}

	string in_dir(argv[1]);
	//TreeBuilder tree_builder(2,"./test","./test");
	TreeBuilder tree_builder(400,in_dir,in_dir);

	/*map<int,int> t_test;
	t_test[8] = 0;
	t_test[9] = 1;
	t_test[100] = 2;
	t_test[50] = 3;


	vector<map<int,int>::iterator > iter_vec(4);
	for(auto it = t_test.begin(); it != t_test.end(); it++){
		cout << "it second: " << it->second << endl;
		iter_vec[it->second] = it;
	}
	cout << "before erase" << endl;
	t_test.erase(iter_vec[2]);
	pair<map<int,int>::iterator,bool> ret = t_test.insert(pair<int,int>(30,2));
	iter_vec[2] = ret.first;

	cout << "after erase" << endl;
	for(int i = 0; i < iter_vec.size(); i++){
		cout << iter_vec[i]->first << " with " << iter_vec[i]->second << endl;
	}
	cout << "xxxxxxxxxxxxxxxxx" << endl;
	for(auto it = t_test.begin(); it != t_test.end(); it++){
		cout << it->first << " with " <<  it->second << endl;
	}
	getchar();*/
}